package leetcode.calc._06_07;

import org.springframework.util.Assert;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *  
 * 示例 1：
 *
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 *
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 2500
 * -104 <= nums[i] <= 104
 *  
 *
 * 进阶：
 *
 * 你可以设计时间复杂度为 O(n2) 的解决方案吗？
 * 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _07_04_300_最长递增子序列 {
    public static void main(String[] args) {
        Solution sol = new _07_04_300_最长递增子序列().new Solution();


        if (true) {
            int[] param = {10,9,2,5,3,7,101,18};
            int res = sol.lengthOfLIS(param);
            int rel = 4;
            Assert.isTrue(rel == res, String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int[] param = {0,1,0,3,2,3};
            int res = sol.lengthOfLIS(param);
            int rel = 4;
            Assert.isTrue(rel == res, String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int[] param = {7,7,7,7,7,7,7};
            int res = sol.lengthOfLIS(param);
            int rel = 1;
            Assert.isTrue(rel == res, String.format("\n%s !=\n%s", res , rel));
        }
        if (true) {
            int[] param = {};
            int res = sol.lengthOfLIS(param);
            int rel = 1;
            Assert.isTrue(rel == res, String.format("\n%s !=\n%s", res , rel));
        }
    }
    class Solution {
        public int lengthOfLIS(int[] nums) {
            // 使用贪心 + 二分法才是正解
            int num = dfs(nums, 1, nums[0], 1);
            return num;
        }

        private int dfs(int[] nums, int nextIndex, int lastVal, int count) {
            // 数量
            if (nums.length == nextIndex) {
                return count;
            }
            int nextVal = nums[nextIndex];
            int maxCount;
            if (nextVal > lastVal) {
                maxCount = dfs(nums, nextIndex + 1, nextVal, count + 1);
            } else if (nextIndex == lastVal) {
                // 相等忽略
                maxCount = dfs(nums, nextIndex + 1, lastVal, count);
            } else {
                // 忽略或重新计算
                int ignore = dfs(nums, nextIndex + 1, lastVal, count);
                int reCount = dfs(nums, nextIndex + 1, nextVal, 1);
                maxCount = Math.max(
                    // 忽略
                    ignore,
                    // 重新计算
                    reCount
                );
            }
            return maxCount;
        }

    }

}
